package data_structure.offer;

import java.util.ArrayList;
import java.util.Arrays;

public class experiment {

    //insertSort
    public static int[] insertSort(int[] a) {
        int length = a.length;
        int preIndex = 0;
        int current = 0;
        for (int i = 0; i < length - 1; i++) {
            preIndex = i;
            current = a[preIndex + 1];
            while (preIndex >= 0 && a[preIndex] >= current) {
                a[preIndex + 1] = a[preIndex];
                preIndex--;
            }
            a[preIndex + 1] = current;
        }
        return a;
    }

    //shellSort
    public static int[] shellSort(int[] a) {

        int length = a.length;
        int temp, gap = length / 2;
        int preIndex;
        while (gap > 0) {
            for (int i = gap; i < length; i++) {
                temp = a[i];
                preIndex = i - gap;
                while (preIndex >= 0 && a[preIndex] >= temp) {
                    a[preIndex + gap] = a[preIndex];
                    preIndex -= gap;
                }

                a[preIndex + gap] = temp;
            }
            gap /= 2;
        }
        return a;
    }

    //mergeSort
    public static int[] mergeSort(int[] a) {

        if (a.length < 2) {
            return a;
        }
        int length = a.length;
        int mid = length / 2;

        int[] left = Arrays.copyOfRange(a, 0, mid);
        int[] right = Arrays.copyOfRange(a, mid, length);

        return merge(mergeSort(left), mergeSort(right));
    }

    public static int[] merge(int[] left, int[] right) {

        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {

            if (i >= left.length) {
                result[index] = right[j++];
            } else if (j >= right.length) {
                result[index] = left[i++];
            } else if (left[i] >= right[j]) {
                result[index] = right[j++];
            } else {
                result[index] = left[i++];
            }
        }
        return result;
    }

    //quickSort
    public static int[] quickSort(int[] a, int start, int end) {

        if (start < 0 || end < start || end >= a.length) {
            return null;
        }
        int smallIndex = partion(a, start, end);
        if (start < smallIndex) {
            quickSort(a, start, smallIndex - 1);
        }
        if (smallIndex < end) {
            quickSort(a, smallIndex + 1, end);
        }
        return a;
    }

    public static int partion(int[] a, int start, int end) {

        int pivot = (int) (start + Math.random() * (end - start + 1));
        swap(a, pivot, end);
        int smallIndex = start - 1;
        for (int i = start; i <= end; i++) {
            if (a[i] <= a[end]) {
                smallIndex++;
                if (i > smallIndex) {
                    swap(a, smallIndex, i);
                }
            }
        }
        return smallIndex;
    }

    public static void swap(int[] a, int start, int end) {

        int temp;
        temp = a[start];
        a[start] = a[end];
        a[end] = temp;
    }

    //heapSort
    //定义全局变量
    static int len;

    public static int[] heapSort(int[] a) {
        if (a.length < 1) {
            return null;
        }
        len = a.length;
        //构建最大堆
        buildMaxHeap(a);

        //取值
        while (len > 0) {
            swap(a, 0, len - 1);
            len--;
            //重新调整为最大堆
            adjustHeap(a, 0);
        }
        return a;
    }

    //从底部向上构建最大堆
    public static void buildMaxHeap(int[] a) {
        for (int i = (a.length / 2 - 1); i >= 0; i--) {
            adjustHeap(a, i);
        }
    }

    public static void adjustHeap(int[] a, int i) {
        int maxIndex = i;
        if (2 * i < len && a[2 * i] > a[maxIndex]) {
            maxIndex = 2 * i;
        }

        if (2 * i + 1 < len && a[2 * i + 1] > a[maxIndex]) {
            maxIndex = 2 * i + 1;
        }

        if (maxIndex != i) {
            swap(a, i, maxIndex);
            adjustHeap(a, maxIndex);
        }
    }

    //countSort
    public static int[] countSort(int[] a) {

        if (a.length < 1) {
            return null;
        }
        int length = a.length;
        //获取最大值和最小值
        int min = a[0], max = a[0];
        for (int i = 0; i < length; i++) {

            if (a[i] >= max) {
                max = a[i];
            }
            if (a[i] < min) {
                min = a[i];
            }
        }
        int bias = 0 - min;//基准值,方便运算
        int[] bucket = new int[max - min + 1];
        //装桶
        for (int i = 0; i < length; i++) {
            bucket[a[i] + bias]++;
        }
        //出桶
        int index = 0, i = 0;
        while (index < length) {
            if (bucket[i] != 0) {
                a[index] = i - bias;
                index++;
                bucket[i]--;
            } else {
                i++;
            }
        }
        return a;
    }

    public static ArrayList<Integer> bucketSort(ArrayList<Integer> a, int bucketSize) {
        if (a.size() < 2) {
            return a;
        }
        int max=a.get(0);
        int min=a.get(0);
        for (int i = 0; i < a.size(); i++) {
            if (max < a.get(i)) {
                max = a.get(i);
            }
            if (min >= a.get(i)) {
                min = a.get(i);
            }
        }
        //确定桶的数量
        int bucketCount = (max - min) / bucketSize + 1;
        ArrayList<ArrayList<Integer>> bucket = new ArrayList<>(bucketCount);

        for (int i = 0; i < bucketCount; i++) {
            bucket.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < a.size(); i++) {
            bucket.get((a.get(i) - min) / bucketSize).add(a.get(i));
        }
        ArrayList<Integer> result = new ArrayList<Integer>();
        for (int i = 0; i < bucketCount; i++) {
            if (bucketSize == 1) {

                for (int j = 0; j < bucket.get(i).size(); j++) {
                    result.add(bucket.get(i).get(j));
                }
            }
            else{
                if (bucketCount == 1) {
                    bucketSize--;
                }
                ArrayList<Integer>temp=bucketSort(bucket.get(i), bucketSize);
                for (int j = 0; j < temp.size(); j++) {
                    result.add(temp.get(j));
                }
            }
        }
        return result;
    }

    public static int[] radixSort(int []a){
        if(a.length == 0){
            return null;
        }
        //找到最大值
        int max=a[0];
        for (int i = 1; i < a.length; i++) {
            if(max<a[i]){
                max=a[i];
            }
        }
        //确定基数
        int maxDiv=0;
        while(max>0){
            maxDiv++;
            max/=10;
        }
        //创建桶加以初始化
        ArrayList<ArrayList<Integer>>bucket=new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            bucket.add(new ArrayList<Integer> ());
        }
        //开始遍历桶
        int mod=10,div=1;
        for(int i=0;i<maxDiv;i++,mod*=10,div*=10){
            //装完桶之后，立马出桶
            for(int j=0;j<a.length; j++){
                int num=(a[j]%mod)/div;
                bucket.get(num).add(a[j]);
            }

            int index=0;
            for(int m=0;m<bucket.size();m++){
                for(int n=0;n<bucket.get(m).size();n++){
                    a[index++]=bucket.get(m).get(n);
                }
                //完成遍历桶的操作之后，立马清空
                bucket.get(m).clear();
            }
        }
        return a;
    }


//    public static int[] countSort(int[] array) {
//        //找到数组的最大值和最小值
//        int min = array[0];
//        int max = array[0];
//        for (int i = 0; i < array.length; i++) {
//            if (min >= array[i]) {
//                min = array[i];
//            }
//            if (max <= array[i]) {
//                max = array[i];
//            }
//        }
//        int bias = 0 - min;
//        int[] bucket = new int[max - min + 1];
//
//        for (int i = 0; i < array.length; i++) {
//            bucket[array[i] + bias]++;
//        }
//
//        int index = 0;
//        for (int i = 0; i < bucket.length; i++) {
//            while (bucket[i] > 0) {
//                array[index++] = i - bias;
//                bucket[i]--;
//            }
//        }
//        return array;
//    }
//
//    //bucketSort
//    public static int[] bucketSort(int[] array, int bucketSize) {
//        if (array.length <= 1) {
//            return array;
//        }
//        int min = array[0];
//        int max = array[0];
//        for (int i = 0; i < array.length; i++) {
//            if (min >= array[i]) {
//                min = array[i];
//            }
//            if (max <= array[i]) {
//                max = array[i];
//            }
//        }
//        int bucketCount = (max - min) / bucketSize + 1;
//        ArrayList<ArrayList<Integer>> bucket = new ArrayList<>(bucketCount);
//
//        for (int i = 0; i < bucketCount; i++) {
//            bucket.add(new ArrayList<>());
//        }
//
//        for (int i = 0; i < array.length; i++) {
//            bucket.get(((array[i] - min) / bucketSize)).add(array[i]);
//        }
//        int[] result = new int[array.length];
//        int index = 0;
//        for (int i = 0; i < bucket.size(); i++) {
//            if (bucketSize == 1) {
//                for (int j = 0; j < bucket.get(i).size(); j++) {
//                    result[index++] = bucket.get(i).get(j);
//                }
//            } else {
//                if (bucketCount == 1) {
//                    bucketSize--;
//                }
//                int[] middle = new int[bucket.get(i).size()];
//                for (int k = 0; k < bucket.get(i).size(); k++) {
//                    middle[k] = bucket.get(i).get(k);
//                }
//
//                int[] temp = bucketSort(middle, bucketSize);
//                for (int value : temp) {
//                    result[index++] = value;
//                }
//
//            }
//        }
//
//        return result;
//    }
//
//    //radixSort
//    public static int[] radixSort(int[] array) {
//
//        if (array.length <= 1) {
//            return array;
//        }
//        int max = 0;
//        for (int value : array) {
//            max = Math.max(max, value);
//        }
//        int maxDix = 0;
//        while (max > 0) {
//            maxDix++;
//            max /= 10;
//        }
//
//        ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
//        for (int i = 0; i < 10; i++) {
//            buckets.add(new ArrayList<>());
//        }
//
//        int mod = 10;
//        int div = 1;
//
//        for (int i = 0; i < maxDix; i++, mod *= 10, div *= 10) {
//
//            for (int j = 0; j < array.length; j++) {
//                int value = array[j] % mod / div;
//                buckets.get(value).add(array[j]);
//            }
//            int index = 0;
//            for (int m = 0; m < buckets.size(); m++) {
//
//                for (int n = 0; n < buckets.get(m).size(); n++) {
//                    array[index++] = buckets.get(m).get(n);
//                }
//                buckets.get(m).clear();
//            }
//        }
//        return array;
//    }

}
